解题思路

首先问题的意思是，在 n × m 格木板上有一些硬币，硬币个数最多为一个。现在机器人从左上角出发至右下角，每次只能右移 or 下移一格，求机器人最多收集多少硬币。

设有硬币的格子为 1，用数组 Arr[ n ][ m ] 保存地图值；令截止到达第 i 行第 j 列收集的最多硬币数为 F（i，j） 。 现在我们来考虑一般情况，对于每个格子我们有两种到达方式：从左边过来<--or-->从上边下来 从左边过来：那么收集的最多硬币数 F（i，j）= F（i，j - 1）+ Arr[ i ][ j ]； 从上边下来：那么收集的最多硬币数 F（i，j）= F（i - 1，j）+ Arr[ i ][ j ]；

此时我们就得到了递推方程： F（i，j）= max{ F（i，j - 1），F（i - 1，j）} + Arr[ i ][ j ]；

现在我们考虑一下退出条件（特殊情况）： 当 i = 1 时，无法从上边下来，此时我们将 F（0，j）= 0； 当 j = 1 时，无法从左边过来，此时我们将 F（i，0）= 0； 如下图，这样就满足 F（i，j）= max{ F（i，j - 1），F（i - 1，j）} + Arr[ i ][ j ]； 这样就构建一个递归函数解题。

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int arr[1005][1005];        //建立一个map

int Max(int a, int b)       //求最大值
{
    return a > b ? a : b;
}

void MaxValue(int n, int m)         //逐行求出最优解
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            arr[i][j] = Max(arr[i - 1][j], arr[i][j - 1]) + arr[i][j];
}

int main()
{
    memset(arr, 0, sizeof(arr));
    int n,m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)    //从元素位置 1 开始逐列（行）对齐
        for (int j = 1; j <= m; j++)
            scanf("%d", &arr[i][j]);

    MaxValue(n, m);
    printf("%d\n", arr[n][m]);    //最后一个即为最优解

    return 0;
}